package others;

import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
 *
 * 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
 * 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
 *
 * 进阶:
 *
 * 你是否可以在 O(1) 时间复杂度内完成这两种操作？
 *
 * 示例:
 *
 * LRUCache cache = new LRUCache( 2 /* 缓存容量 );
        *
        *cache.put(1,1);
        *cache.put(2,2);
        *cache.get(1);       // 返回  1
        *cache.put(3,3);    // 该操作会使得密钥 2 作废
        *cache.get(2);       // 返回 -1 (未找到)
        *cache.put(4,4);    // 该操作会使得密钥 1 作废
        *cache.get(1);       // 返回 -1 (未找到)
        *cache.get(3);       // 返回  3
        *cache.get(4);       // 返回  4
        *
        *来源：力扣（LeetCode）
        *链接：https://leetcode-cn.com/problems/lru-cache
        *著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//public class LRUCache extends LinkedHashMap<Integer, Integer> {
//
//    private int capacity;
//    public LRUCache(int capacity) {
//        super(capacity, 0.75f, true);
//        this.capacity = capacity;
//    }
//
//    public int get(int key) {
//       return super.getOrDefault(key, -1);
//    }
//
//    public void put(int key, int value) {
//        super.put(key, value);
//    }
//
//    @Override
//    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
//        return size() > this.capacity;
//    }
//}

public class LRUCache{

    class DLinkNode{
        int key;
        int value;
        DLinkNode next;
        DLinkNode prev;
        DLinkNode(){}
        DLinkNode(int k, int v){
            value = v;
            key = k;
        }
    }

    private DLinkNode head;
    private DLinkNode tail;
    private Map<Integer, DLinkNode> cache = new HashMap<>();
    private int size;
    private int capacity;

    public LRUCache(int capacity) {
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        DLinkNode node = cache.get(key);
        if(node != null){
            moveToHead(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {

        DLinkNode node = cache.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);
        } else {
            node = new DLinkNode(key, value);
            cache.put(key, node);
            addNode(node);
            size ++;
            if(size > capacity){
                DLinkNode n = popTail();
                cache.remove(n.key);
                size --;
            }
        }
    }

    private void addNode(DLinkNode node){
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void moveToHead(DLinkNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
        addNode(node);
    }

    private DLinkNode popTail(){
        if(size > 0){
            DLinkNode node = tail.prev;
            node.prev.next = tail;
            tail.prev = node.prev;
            return node;
        }
        return null;
    }

}